home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / ien / ien-109 < prev    next >
Text File  |  1988-12-01  |  48KB  |  1,609 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.                      HOW TO BUILD A GATEWAY
  29.  
  30.                        Virginia Strazisar
  31.  
  32.                             IEN #109
  33.  
  34.                          August 31, 1979
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.                         TABLE OF CONTENTS
  42.  
  43.  1.  Introduction...............................................1
  44.  
  45.  2.  Information Maintained by Gateways.........................1
  46.  
  47.  3.  Initialization.............................................3
  48.  
  49.  4.  Determining Connectivity to Networks.......................3
  50.  
  51.  5.  Determining Connectivity to Neighbors......................4
  52.  
  53.  6.  Exchanging Routing Information.............................4
  54.  
  55.  7.  Computing Routes...........................................5
  56.  
  57.  8.  Forwarding Traffic.........................................7
  58.  
  59.  9.  Non-Routing Gateways.......................................7
  60.  
  61. 10.  Adding New Neighbors and Networks..........................8
  62.  
  63. 11.  Communications with Hosts..................................9
  64.  
  65. 12.  Future Modifications......................................10
  66.  
  67. 13.  Packet Formats............................................11
  68.  
  69. 14.  Examples..................................................19
  70.  
  71. 15.  Tables and Variables......................................23
  72.  
  73. 16.  Events and Responses......................................25
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80. 1.  Introduction
  81.  
  82. This is a description of how to implement a gateway.  The gateway
  83. forwards internet traffic formatted as  described  in  IEN  #111,
  84. "Internet Protocol".  The gateway polls its attached networks and
  85. neighbor  gateways  to  determine  its connectivity to them, then
  86. exchanges this information with its neighbor gateways in order to
  87. compute routes to each network in the catenet.  When gateways  or
  88. network interfaces fail, the gateways compute alternate routes to
  89. the networks.
  90.  
  91. The  design  for  this  gateway  routing  strategy was originally
  92. presented  in  IEN  #30,  "Gateway  Routing,  An   Implementation
  93. Specification".   That  document  gives an overview of the design
  94. and explains some of the decisions made in designing this routing
  95. strategy.  Since IEN #30 was released, this routing strategy  has
  96. been  implemented  in  several  gateways.  During implementation,
  97. several modifications were made to  the  original  design,  thus,
  98. those  sections of IEN #30 covering the detailed specification of
  99. the design are obsolete and are replaced by this document.
  100.  
  101. 2.  Information Maintained by Gateways
  102.  
  103. Gateways must maintain information about  their  connectivity  to
  104. networks  and  other  gateways.  The functional description below
  105. explains how this information is obtained  and  modified  by  the
  106. gateways.   For  the purpose of explaining the gateway functions,
  107. this information is  organized  into  the  following  tables  and
  108. variables.
  109.  
  110. Number of Networks
  111.  
  112. The  number  of  networks for which the gateway maintains routing
  113. information and to which it can forward  packets.   The  gateways
  114. maintain  and  exchange  routing  information  indexed by network
  115. numbers.  Thus, the Number of Networks also  corresponds  to  the
  116. highest  numbered network to which the gateway can route traffic.
  117. (Network numbers are listed in IEN #117, "Assigned Numbers".)
  118.  
  119.  
  120. Number of Neighbors
  121.  
  122. The number of neighbor gateways with which the gateway  exchanges
  123. routing  information.   A  neighbor  gateway  of gateway X is any
  124. gateway that has an interface on the same network as  gateway  X.
  125. If  gateway  X  and  its  neighbor  have more than one network in
  126. common, then each neighbor gateway  interface  on  a  network  to
  127. which  gateway  X  is  attached  is  considered  to be a separate
  128. neighbor.
  129.  
  130.  
  131.  
  132.                               - 1 -
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139. Gateway Addresses
  140.  
  141. The address of the  gateway  on  each  network  to  which  it  is
  142. attached.
  143.  
  144. Neighbor Addresses
  145.  
  146. The addresses of the neighbor gateways.
  147.  
  148. Connectivity to Neighbors
  149.  
  150. A  vector  of  the status of connectivity between the gateway and
  151. each of its neighbor gateways.  The connectivity is determined by
  152. polling the neighbors.
  153.  
  154. Routing Updates
  155.  
  156. The routing updates that are sent to the neighbor gateways.  Each
  157. routing update contains the distance from  the  gateway  to  each
  158. network.  There is one routing update for each neighbor.
  159.  
  160. Distance Matrix
  161.  
  162. A  matrix  of  the  routing  updates  received  from  each of the
  163. neighbor gateways.  Routing updates contain the distance  from  a
  164. gateway to each network.
  165.  
  166. Minimum Distance Vector
  167.  
  168. A  vector  of  the minimum distance to each network.  Distance is
  169. measured in networks traversed;  a gateway  which  is  physically
  170. attached  to  a  network  is  zero hops from that network; if the
  171. gateway must send through one other gateway to get to a  network,
  172. then it is one hop from that network.
  173.  
  174. Routing updates from non-routing neighbor gateways
  175.  
  176. A  routing  update  for  each  neighbor  gateway  that  does  not
  177. participate in this routing scheme.  This is the update that  the
  178. gateway  would  receive  from  this  neighbor if the neighbor did
  179. participate in routing.
  180.  
  181. Routing Table
  182.  
  183. A table containing, for each network,  a  list  of  the  neighbor
  184. gateways on a minimum length route to that network.
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.                               - 2 -
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198. Send Sequence Number
  199.  
  200. The  sequence  number  that  the gateway will use to transmit the
  201. next routing update to its neighbors.
  202.  
  203. Receive Sequence Numbers
  204.  
  205. The sequence number that the gateway received in the last routing
  206. update from each of its neighbors.  There is  a  sequence  number
  207. for each neighbor.
  208.  
  209. 3.  Initialization
  210.  
  211. The gateway is initialized with the following information:
  212.  
  213. The gateway's address on each network to which it is attached.
  214.  
  215. The addresses of its neighbors.
  216.  
  217. A  routing  update from each of its neighbor gateways that do not
  218. participate in routing.
  219.  
  220. Initially, the  gateway  should  assume  that  all  its  neighbor
  221. gateways are down, that it is disconnected from networks to which
  222. it is attached, and that the distance reported in routing updates
  223. from  each  neighbor  to each network is infinity (see "Computing
  224. Routes").
  225.  
  226. 4.  Determining Connectivity to Networks
  227.  
  228. The gateway must determine its connectivity to networks to  which
  229. it is physically attached.  The gateway is connected to a network
  230. if  it  can send and receive internet packets on its interface to
  231. that network.  The method that the gateway uses to determine  its
  232. connectivity   to  a  network  is  network  dependent.   In  some
  233. networks, the host to network protocol determines whether or  not
  234. data  packets can be sent and received on the host interface.  In
  235. these networks, the gateway can simply check  status  information
  236. provided  by  the  protocol  in  order  to  determine  if  it can
  237. communicate with the network.  In other networks, where the  host
  238. to  network  protocols  are less complex, it may be necessary for
  239. the gateway to send traffic to itself  to  determine  if  it  can
  240. communicate  with  the  network.  In these networks, the gateways
  241. can periodically poll the network to  determine  if  the  network
  242. interface is operational.
  243.  
  244. For  purposes  of  computing distances and routes to networks, if
  245. the  gateway  can  send  and  receive  traffic  on  its   network
  246. interface, then its distance to the network is zero; if it cannot
  247. send  and  receive traffic on the interface, then its distance to
  248.  
  249.  
  250.                               - 3 -
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257. the network is  infinity.   Note  that  if  a  gateway's  network
  258. interface is not working, it may still be able to send traffic to
  259. the  network  on  an  alternate  route  via  one  of its neighbor
  260. gateways.
  261.  
  262. 5.  Determining Connectivity to Neighbors
  263.  
  264. A neighbor gateway is in one  of  three  states:   up,  down,  or
  265. recovering.   In  the  latter  case, the gateway has communicated
  266. with its neighbor, and  is  in  a  waiting  period  to  determine
  267. whether  it  will  be  able  to  continue to communicate with the
  268. neighbor.  This state exists to prevent a gateway  from  using  a
  269. neighbor  gateway  to forward traffic when communications between
  270. it and the neighbor are extremely lossy.  The gateway  determines
  271. its connectivity to each neighbor gateway as follows.  Initially,
  272. the  neighbor is assumed to be "down".  The gateway sends an echo
  273. packet (see "Packet Formats") to the  neighbor  gateway  every  N
  274. seconds  and  increments  a  count of echo packets outstanding to
  275. that neighbor.  When the gateway receives an  echo  reply  packet
  276. from  the  neighbor,  it  clears  the  count  of outstanding echo
  277. packets.  If that neighbor was "down", the gateway  starts  an  X
  278. second  timer and sets the neighbor's status to "recovering".  If
  279. after X seconds, the neighbor's  status  is  still  "recovering",
  280. then  the  neighbor's status is changed to "up".  If the count of
  281. echo packets outstanding  to  a  neighbor  is  equal  to  Z,  the
  282. neighbor's  status  is set to "down".  As probes are sent every N
  283. seconds, a neighbor's status is changed to "down" if it does  not
  284. respond within (N * Z) seconds.  Note that the waiting period, X,
  285. during  which  the neighbor's status is "recovering" should be at
  286. least several times the  interval  (N  *  Z  seconds)  needed  to
  287. declare  the neighbor "down".  This prevents the neighbor gateway
  288. from cycling rapidly between the "up" and "down" states.
  289.  
  290. The gateway maintains a vector of the connectivity between it and
  291. its neighbors.  This vector is used in  computing  distances  and
  292. routes to networks.  The vector contains K entries where K is the
  293. number  of neighbors.  If the state of the Jth neighbor is either
  294. "down" or "recovering", then the Jth entry of the vector  is  set
  295. to  infinity;  if  the state of the Jth neighbor is "up" then the
  296. Jth entry of the vector is set to one.
  297.  
  298. 6.  Exchanging Routing Information
  299.  
  300. The gateway receives and transmits routing  information  reliably
  301. using   sequence   numbered  packets  and  a  retransmission  and
  302. acknowledgement scheme.  This scheme works as follows.  For  each
  303. neighbor,  the  gateway remembers the Receive Sequence Number, R,
  304. that it received in the most  recent  routing  packet  from  that
  305. neighbor.   This  value  is  initialized  by  setting  it  to the
  306. sequence number received in the  first  routing  packet  received
  307.  
  308.  
  309.                               - 4 -
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316. from  a neighbor after that neighbor's status is set to "up".  On
  317. receipt  of  a  routing  packet  from  a  neighbor,  the  gateway
  318. subtracts  the  Receive  Sequence  Number,  R,  from the sequence
  319. number in the routing packet, S. If this value (S-R)  is  greater
  320. than  or  equal  to  zero,  then  the gateway accepts the routing
  321. packet, sends an acknowledgement to the neighbor  containing  the
  322. sequence  number  S, and replaces the Receive Sequence Number, R,
  323. with S.  If this value (S-R)  is  less  than  zero,  the  gateway
  324. rejects  the  routing packet and sends a negative acknowledgement
  325. to the neighbor with sequence number R.
  326.  
  327. The gateway has a Send Sequence Number, N,  for  sending  routing
  328. packets  to  all  of  its neighbors.  This sequence number can be
  329. initialized  to  any  value.   The  Send   Sequence   Number   is
  330. incremented  each  time  a  new  routing  update  is created.  On
  331. receiving an acknowledgement for a routing  update,  the  gateway
  332. subtracts  the  sequence  number  acknowledged,  A, from the Send
  333. Sequence Number, N.  If the value (N-A) is non-zero, then an  old
  334. routing  update  is being acknowledged.  The gateway continues to
  335. retransmit the most recent routing update to  the  neighbor  that
  336. sent  the  acknowledgement.  If (N-A) is zero, the routing update
  337. has been acknowledged.  Note that only the  most  recent  routing
  338. update  need  be  acknowledged;  if  a  second  routing update is
  339. generated before the first routing update is  acknowledged,  only
  340. the second routing update need be acknowledged.
  341.  
  342. If  a negative acknowledgement is received, the gateway subtracts
  343. the sequence number negatively acknowledged,  A,  from  its  Send
  344. Sequence  Number, N.  If this value (N-A) is less than zero, then
  345. the gateway replaces  its  Send  Sequence  Number,  N,  with  the
  346. sequence  number  negatively  acknowledged  plus  one,  A+1,  and
  347. retransmits the update to all its neighbors.  If (N-A) is greater
  348. than or equal to zero, then the gateway continues  to  retransmit
  349. the routing update using sequence number N.  In order to maintain
  350. the  correct  sequence  numbers  at all gateways, routing updates
  351. must be retransmitted to  all  neighbors  if  the  Send  Sequence
  352. Number  changes, even if the routing information does not change.
  353.  
  354. The gateway retransmits routing updates periodically  until  they
  355. are  acknowledged  and whenever its Send Sequence Number changes.
  356. The gateway sends routing updates only to neighbors that  are  in
  357. the "up" state, not to neighbors that are "down" or "recovering".
  358. Examples of the sequence number strategy are given below.
  359.  
  360. 7.  Computing Routes
  361.  
  362. A  routing  update contains the number of networks that a gateway
  363. is reporting about followed by a list of the distances  to  these
  364. networks,  indexed  by network number.  Assuming that the gateway
  365. has checked the sequence number of a routing update that  it  has
  366.  
  367.  
  368.                               - 5 -
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375. received and has decided to accept the update, the information in
  376. the update is processed as follows.
  377.  
  378. The  gateway  contains  a  N  x K distance matrix, where N is the
  379. number of networks and K is the number of neighbor gateways.   An
  380. entry  in  this matrix, represented as d(I,J), is the distance to
  381. network I from neighbor J as reported in the most recent  routing
  382. update  from  neighbor  J.   The  gateway  also contains a vector
  383. indicating the  connectivity  between  itself  and  its  neighbor
  384. gateways.   The  values  in this vector are computed as discussed
  385. above (see "Determining Connectivity to Neighbors").   The  value
  386. of  the  Jth  entry  of  this  vector,  which is the connectivity
  387. between the gateway and the Jth neighbor, is represented as d(J).
  388.  
  389. The gateway copies the  routing  update  received  from  the  Jth
  390. neighbor  into  the  appropriate row of the distance matrix, then
  391. updates its routes as follows.  The gateway calculates a  minimum
  392. distance  vector, containing the minimum distance to each network
  393. from the gateway.  The Ith entry of this vector,  represented  as
  394. MinD(I) is:
  395.  
  396.         MinD(I) = minimum over all neighbors of d(J) + d(I,J)
  397.  
  398. where  d(J)  is  the  distance  between  the  gateway and the Jth
  399. neighbor and d(I,J) is the distance from the Jth neighbor to  the
  400. Ith  network.   If the Ith network is attached to the gateway and
  401. the gateway can send and receive traffic on its network interface
  402. (see "Determining Connectivity to Networks"),  then  the  gateway
  403. sets the Ith entry of the minimum distance vector to zero.
  404.  
  405. Using the minimum distance vector, the gateway computes a list of
  406. neighbor  gateways through which to send traffic to each network.
  407. The entry for network I contains all neighbors such that:
  408.  
  409.         MinD(I) = d(J) + d(I,J)
  410.  
  411. In other words, the entry for network I  contains  all  neighbors
  412. such  that the distance from the gateway to the neighbor plus the
  413. distance from the neighbor to the network is equal to the minimum
  414. distance from the gateway to the network.
  415.  
  416. After updating its routes to the networks, the  gateway  computes
  417. the  new  routing updates to be sent to its neighbors as follows.
  418. For each neighbor, J, the gateway  constructs  a  routing  update
  419. which is a N entry vector where N is the number of networks.  The
  420. Jth entry of this vector is:
  421.  
  422.         MinD(I) if MinD(I) less than or equal to d(I,J)
  423.         infinity if MinD(I) greater than d(I,J)
  424.  
  425.  
  426.  
  427.                               - 6 -
  428.  
  429.  
  430.  
  431.  
  432.  
  433.  
  434. where  d(I,J)  is  the  distance from the Jth neighbor to the Ith
  435. network and MinD(I) is the minimum distance from the  gateway  to
  436. the  Ith  network.   In  other  words,  the  gateway  reports its
  437. distance to a network to a neighbor only if it is as close to  or
  438. closer to a network than its neighbor.
  439.  
  440. Finally,  the  gateway  must  determine  whether  it  should send
  441. routing updates to its neighbors.  The gateway maintains  a  copy
  442. of  the  most  recent routing updates that it sent to each of its
  443. neighbors.  The gateway computes the new routing updates to  send
  444. to  each  of  its neighbors.  If any of these routing updates are
  445. different than the preceding updates, then the gateway sends  new
  446. routing  updates to its neighbors.  If no routing information has
  447. changed since the last routing update was sent, then the  gateway
  448. does  not  need  to  send new routing updates.  The gateway sends
  449. routing updates only to neighbors that are currently in the  "up"
  450. state.
  451.  
  452. The  gateway  requests routing updates from neighbors that are in
  453. the "up" state, but have not yet sent a  routing  update  to  it.
  454. Routing  updates  are requested by setting the appropriate bit in
  455. the routing update being sent (see "Packet Formats").  Similarly,
  456. if a gateway receives a routing update from a neighbor  in  which
  457. the bit requesting a routing update is set, the gateway sends the
  458. neighbor the most recent routing update.
  459.  
  460. 8.  Forwarding Traffic
  461.  
  462. On  receipt of a packet to be forwarded, the gateway extracts the
  463. internet destination network  field  from  the  packet.   If  the
  464. gateway  is attached to the network, and its network interface is
  465. operational, then the gateway  simply  composes  the  appropriate
  466. local  network  header  for the destination network and sends the
  467. packet.
  468.  
  469. If the gateway is not connected to the network, then the  gateway
  470. checks  the list of the neighbors on the route to the destination
  471. network.  If there are no neighbors on the list, then the gateway
  472. drops the packet and sends the  internet  source  a  "destination
  473. unreachable" message (see "Communications with Hosts").
  474.  
  475. If  there are one or more neighbors on a route to the destination
  476. network, then the gateway  sends  the  packet  to  one  of  these
  477. neighbors.   If  there  is  more  than  one  neighbor,  then  the
  478. neighbors are used in a round robin fashion.
  479.  
  480. 9.  Non-Routing Gateways
  481.  
  482. Non-routing gateways are gateways that forward internet  traffic,
  483. but  that  do  not  participate in this routing scheme.  Whenever
  484.  
  485.  
  486.                               - 7 -
  487.  
  488.  
  489.  
  490.  
  491.  
  492.  
  493. possible,  traffic  is  forwarded  only  through  gateways   that
  494. participate  in  this  routing  scheme.  Non-routing gateways are
  495. used to forward traffic only if they provide the only route to  a
  496. network.   These  gateways  are  used  as  follows.   Consider  a
  497. gateway, G1.  The only non-routing gateways that it needs to know
  498. about are its neighbor gateways, as these are the  gateways  from
  499. which  it  would  normally  receive  routing  updates.   For each
  500. non-routing neighbor gateway of gateway G1, compute  the  routing
  501. update  that  would  be sent to G1 assuming that all gateways and
  502. network connections are operational.  These routing  updates  are
  503. assembled  in  G1.   The  gateway, G1, first computes its minimum
  504. distance vector  as  explained  above,  using  only  the  routing
  505. updates  from  neighbors  that  participate  in  routing.  If the
  506. minimum distance to any network is infinity, i.e. the network  is
  507. unreachable  via  any  of  the routing gateways, then the minimum
  508. distance to that network is re-computed using the routing  update
  509. compiled  for  the non-routing neighbor gateway.  For purposes of
  510. computing the minimum distance to a  network,  the  gateway,  G1,
  511. assumes that the distance between itself and the neighbor gateway
  512. is  zero.   After  computing  the  minimum  distance  vector, the
  513. gateway compiles the list of neighbor gateways through  which  to
  514. send  traffic  to  each  network and sends routing updates to its
  515. neighbors as  explained  above  (see  "Computing  Routes").   The
  516. gateway does not send routing updates to the non-routing neighbor
  517. gateways.
  518.  
  519. 10.  Adding New Neighbors and Networks
  520.  
  521. Gateways  dynamically add routing information about new neighbors
  522. and new networks to their tables.  The gateway maintains  a  list
  523. of   neighbor  gateway  addresses.   When  a  routing  update  is
  524. received, the gateway searches this list  of  addresses  for  the
  525. internet  source  address  of  the routing update packet.  If the
  526. internet source address of the routing update is not contained in
  527. the list of neighbor addresses, the gateway adds this address  to
  528. the  list of neighbor addresses.  The gateway accepts the routing
  529. update, sets the neighbor's  connectivity  status  to  "up",  and
  530. computes  new routes as explained above.  The gateway also begins
  531. polling this new neighbor to monitor its connectivity.  Note that
  532. this strategy requires that one gateway in each pair of  neighbor
  533. gateways  must  have  the  neighbor's  address  assembled  in its
  534. tables.  The newest gateway can  be  given  a  complete  list  of
  535. neighbors,  thus  avoiding the need to re-assemble older gateways
  536. when new gateways are installed.
  537.  
  538. Gateways  obtain  routing  information  about  new  networks   as
  539. follows.  The gateway maintains a count of the number of networks
  540. for  which  it currently contains routing information, N.  When a
  541. routing update is received, the gateway compares this  number  to
  542. the  number  of networks reported in the routing update, M.  If M
  543.  
  544.  
  545.                               - 8 -
  546.  
  547.  
  548.  
  549.  
  550.  
  551.  
  552. is greater than N, then the gateway updates the count of networks
  553. for which it maintains routing information  to  include  the  new
  554. networks.   Next,  the  gateway  expands  its  distance matrix to
  555. include the number of networks reported.  The distance matrix  is
  556. the  matrix  of  distances  to  networks  as  reported in routing
  557. updates from the neighbor gateways.  In expanding the matrix, the
  558. gateway assumes the distance to all  new  networks  is  infinity.
  559. After  expanding  the matrix, the gateway computes new routes and
  560. new routing updates as outlined above.
  561.  
  562. Note that expanding neighbor address tables and distance matrices
  563. may present an implementation problem.  In practice, these tables
  564. can be assembled to contain some maximum number of neighbors  and
  565. networks.   If  a  new  neighbor  cannot  be added to a gateway's
  566. tables, then routing updates or echo packets from  that  neighbor
  567. should be ignored.  The new neighbor will assume that the gateway
  568. is  down  and  will  not use it to forward traffic.  If a gateway
  569. cannot add a new network to its  routing  tables,  it  can  still
  570. accept  routing  updates  containing  information  about  the new
  571. network, but it will be  unable  to  route  traffic  to  the  new
  572. network.  The routing updates that it sends to its neighbors will
  573. not  contain  information  about  the  new  network.   Whenever a
  574. gateway receives a  routing  update  that  does  not  report  the
  575. distance  to  a  network,  the  gateway  should  assume  that the
  576. distance is infinity.
  577.  
  578. 11.  Communications with Hosts
  579.  
  580. The  gateway  sends  messages  to  internet  hosts   in   several
  581. situations:    when   the   gateway  cannot  reach  the  internet
  582. destination,  when  the  gateway  does  not  have  the  buffering
  583. capacity to forward a packet, and when the gateway can direct the
  584. host  to  send  traffic on a shorter route.  These situations are
  585. explained in more detail below.  The formats  for  messages  sent
  586. from  a  gateway  to  a  host  are  given  in the section "Packet
  587. Formats".
  588.  
  589. If, according to the information in the gateway's routing tables,
  590. the network specified in the  internet  destination  field  of  a
  591. packet  is  unreachable,  i.e.  the  distance  to  the network is
  592. infinity, the gateway sends a destination unreachable message  to
  593. the  internet  source  host  of the packet.  In addition, in some
  594. networks, the gateway may be able to determine  if  the  internet
  595. destination  host is unreachable.  Gateways in these networks may
  596. send destination unreachable messages to the source host when the
  597. destination host is unreachable.
  598.  
  599. The gateway may discard internet packets if it does not have  the
  600. buffer  space  needed to queue the packets for output to the next
  601. network on the route to the destination network.  If the  gateway
  602.  
  603.  
  604.                               - 9 -
  605.  
  606.  
  607.  
  608.  
  609.  
  610.  
  611. discards  a  packet,  it  sends  a  source  quench message to the
  612. internet source host of the packet.  The source quench message is
  613. a request to the host to cut back the rate at which it is sending
  614. traffic to the internet destination.  The gateway sends a  source
  615. quench message for every message that it discards.  On receipt of
  616. a  source quench message, hosts should cut back the rate at which
  617. they are sending traffic to the specified destination until  they
  618. no  longer  receive source quench messages from the gateway.  The
  619. hosts can then gradually increase the  rate  at  which  they  are
  620. sending  traffic  to  the  destination  until  they again receive
  621. source quench messages from the gateway.
  622.  
  623. The gateway sends a redirect message to a host in  the  following
  624. situation.   A  gateway,  G1,  receives an internet packet from a
  625. host on a network to which the gateway is attached.  The gateway,
  626. G1, checks its routing table and obtains the address of the  next
  627. gateway,  G2,  on  the route to the packet's internet destination
  628. network, X.  If G2 and the host identified by the internet source
  629. address of the packet are on the same network, a redirect message
  630. is sent to the host.  The redirect message advises  the  host  to
  631. send  its traffic for network X directly to gateway G2 as this is
  632. a shorter path to the  destination.   The  gateway  forwards  the
  633. original data packet to its internet destination.
  634.  
  635. 12.  Future Modifications
  636.  
  637. As  there  are  now  many networks planned or implemented, and as
  638. these networks may be assigned a wide range of  network  numbers,
  639. it  is  no  longer  feasible  to  maintain routing information in
  640. tables indexed by network numbers.  Gateways will be modified  to
  641. use  a  hash  table scheme to convert network numbers to internal
  642. indices to reference routing tables.  The information in  routing
  643. updates  exchanged  by  the gateways will no longer be indexed by
  644. network number.  The format of routing updates will  be  modified
  645. to  include  both  the  network  number  and  the distance to the
  646. network.  These modifications will be documented  in  a  separate
  647. note.
  648.  
  649.  
  650.  
  651.  
  652.  
  653.  
  654.  
  655.  
  656.  
  657.  
  658.  
  659.  
  660.  
  661.  
  662.  
  663.                              - 10 -
  664.  
  665.  
  666.  
  667.  
  668.  
  669.  
  670. 13.  Packet Formats
  671.  
  672. Gateway  to  gateway  and  gateway to host communications use the
  673. version 4 internet protocol.  The first octet of the data portion
  674. of the packet is a gateway type field; the value  of  this  field
  675. determines  the  format  of  the  remaining  data.  The format of
  676. internet packets is explained in IEN #111,  "Internet  Protocol".
  677. Unless  otherwise noted under the individual format descriptions,
  678. the values of the internet header fields are as follows:
  679.  
  680. Version                 4
  681.  
  682. IHL                     Internet header length in 32-bit words;
  683.                         this is 5.
  684.  
  685. Type of Service         0
  686.  
  687. Total Length            Length of internet header and data in
  688.                         octets.
  689.  
  690. Identification, Flags,
  691. Fragment Offset         Used in fragmentation, see IEN #111.
  692.  
  693. Time to Live            Time to live in seconds; as this field
  694.                         is decremented at each machine in which
  695.                         the packet is processed, the value in
  696.                         this field should be at least as great as
  697.                         the number of gateways which this packet
  698.                         will traverse.  (This must be considered
  699.                         in the messages sent to hosts.)
  700.  
  701. Protocol                3
  702.  
  703. Header Checksum         The 16 bit one's complement of the one's
  704.                         complement sum of all 16 bit words in the
  705.                         header.  For computing the checksum, the
  706.                         checksum field should be zero.  This
  707.                         checksum may be replaced in the future,
  708.                         see updates of the Internet Protocol
  709.                         Specification.
  710.  
  711. Source Address          The address of the gateway that composes
  712.                         the packet.  Unless otherwise noted, this
  713.                         can be any of the gateway's addresses.
  714.  
  715. Destination Address     The address of the gateway or host to
  716.                         which the packet should be sent.
  717.  
  718.  
  719.  
  720.  
  721.  
  722.                              - 11 -
  723.  
  724.  
  725.  
  726.  
  727.  
  728.  
  729.                          Routing Update
  730.  
  731.  0                   1                   2                   3
  732.  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  733. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  734. ! Gateway Type  !    unused     !         Sequence Number       !
  735. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  736. ! NU !     N    !  Distance 1   !  Distance 2   !  Distance 3   !
  737. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  738.                                 .
  739.                                 .
  740.                                 .
  741. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  742. !  Distance N-3 !  Distance N-2 !  Distance N-1 !  Distance N   !
  743. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  744.  
  745. Gateway Type            1
  746.  
  747. Sequence Number         The 16-bit sequence number used to transmit
  748.                         routing updates.
  749.  
  750. NU                      A 1-bit field.  This bit is set if the
  751.                         source gateway requests a routing update
  752.                         from the destination gateway.
  753.  
  754. N                       The number of networks for which distances
  755.                         are reported in this update.
  756.  
  757. Distance 1..N           A set of octets that are the values in
  758.                         the routing update for distances to
  759.                         network numbers 1 through N.  The network
  760.                         numbers are listed in IEN #117, "Assigned
  761.                         Numbers".  If the Ith network is unreachable,
  762.                         the distance to the network is infinity,
  763.                         which is represented as 177 (octal).
  764.  
  765.  
  766.  
  767.  
  768.  
  769.  
  770.  
  771.  
  772.  
  773.  
  774.  
  775.  
  776.  
  777.  
  778.  
  779.  
  780.  
  781.                              - 12 -
  782.  
  783.  
  784.  
  785.  
  786.  
  787.  
  788.            Acknowledgement or Negative Acknowledgement
  789.  
  790.  0                   1                   2                   3
  791.  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  792. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  793. ! Gateway Type  !    unused     !         Sequence Number       !
  794. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  795.  
  796. Gateway Type            2 for acknowledgement; 10 (decimal) for
  797.                         negative acknowledgement.
  798.  
  799. Sequence Number         The 16-bit sequence number that the gateway
  800.                         is acknowledging or negatively acknowledging.
  801.  
  802.  
  803.  
  804.  
  805.  
  806.  
  807.  
  808.  
  809.  
  810.  
  811.  
  812.  
  813.  
  814.  
  815.  
  816.  
  817.  
  818.  
  819.  
  820.  
  821.  
  822.  
  823.  
  824.  
  825.  
  826.  
  827.  
  828.  
  829.  
  830.  
  831.  
  832.  
  833.  
  834.  
  835.  
  836.  
  837.  
  838.  
  839.  
  840.                              - 13 -
  841.  
  842.  
  843.  
  844.  
  845.  
  846.  
  847.                  Destination Unreachable Packet
  848.  
  849.  0                   1                   2                   3
  850.  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  851. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  852. ! Gateway Type  !     Code      !           unused              !
  853. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  854. !      Internet Header + 64 bits of Original Data Packet        !
  855. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  856.  
  857. Destination Address     The source network and address from the
  858.                         original data packet.
  859.  
  860. Gateway Type            3
  861.  
  862. Code                    0 = net unreachable; 1 = host unreachable.
  863.  
  864. Internet Header + 64 bits
  865. of Data Packet          The internet header plus the first 64 bits
  866.                         of the original data packet.  This data is
  867.                         used by the host to match the message from
  868.                         the gateway to the appropriate process.
  869.                         If a higher level protocol uses port numbers,
  870.                         they are assumed to be in the first 64 data
  871.                         bits of the original data packet.
  872.  
  873.  
  874.  
  875.  
  876.  
  877.  
  878.  
  879.  
  880.  
  881.  
  882.  
  883.  
  884.  
  885.  
  886.  
  887.  
  888.  
  889.  
  890.  
  891.  
  892.  
  893.  
  894.  
  895.  
  896.  
  897.  
  898.  
  899.                              - 14 -
  900.  
  901.  
  902.  
  903.  
  904.  
  905.  
  906.                       Source Quench Packet
  907.  
  908.  0                   1                   2                   3
  909.  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  910. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  911. ! Gateway Type  !                 unused                        !
  912. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  913. !      Internet Header + 64 bits of Original Data Packet        !
  914. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  915.  
  916. Destination Address     The source network and address of the
  917.                         original data packet.
  918.  
  919. Gateway Type            4
  920.  
  921. Internet Header + 64 bits
  922. of Data Packet          The internet header plus the first 64 bits
  923.                         of the original data packet.  This data is
  924.                         used by the host to match the message from
  925.                         the gateway to the appropriate process.
  926.                         If a higher level protocol uses port numbers,
  927.                         they are assumed to be in the first 64 data
  928.                         bits of the original data packet.
  929.  
  930.  
  931.  
  932.  
  933.  
  934.  
  935.  
  936.  
  937.  
  938.  
  939.  
  940.  
  941.  
  942.  
  943.  
  944.  
  945.  
  946.  
  947.  
  948.  
  949.  
  950.  
  951.  
  952.  
  953.  
  954.  
  955.  
  956.  
  957.  
  958.                              - 15 -
  959.  
  960.  
  961.  
  962.  
  963.  
  964.  
  965.                          Redirect Packet
  966.  
  967.  0                   1                   2                   3
  968.  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  969. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  970. ! Gateway Type  !                 unused                        !
  971. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  972. !Gateway Network!           Gateway Address                     !
  973. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  974. !      Internet Header + 64 bits of Original Data Packet        !
  975. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  976.  
  977. Destination Address     The source network and address of the
  978.                         original data packet.
  979.  
  980. Gateway Type            5
  981.  
  982. Gateway Network         Address of the gateway to which traffic
  983. Gateway Address         for the network specified in the
  984.                         internet destination network field of
  985.                         the data packet should be sent.
  986.  
  987. Internet Header + 64 bits
  988. of Data Packet          The internet header plus the first 64 bits
  989.                         of the original data packet.  This data is
  990.                         used by the host to match the message from
  991.                         the gateway to the appropriate process.
  992.                         If a higher level protocol uses port numbers,
  993.                         they are assumed to be in the first 64 data
  994.                         bits of the original data packet.
  995.  
  996.  
  997.  
  998.  
  999.  
  1000.  
  1001.  
  1002.  
  1003.  
  1004.  
  1005.  
  1006.  
  1007.  
  1008.  
  1009.  
  1010.  
  1011.  
  1012.  
  1013.  
  1014.  
  1015.  
  1016.  
  1017.                              - 16 -
  1018.  
  1019.  
  1020.  
  1021.  
  1022.  
  1023.  
  1024.                     Echo or Echo Reply Packet
  1025.  
  1026.  0                   1                   2                   3
  1027.  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  1028. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1029. ! Gateway Type  !                  unused                       !
  1030. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1031.  
  1032. Source Address          In an echo packet, the address of the
  1033.                         gateway on the same network as the neighbor
  1034.                         to which it is sending the echo packet.
  1035.                         In an echo reply packet, the source and
  1036.                         destination addresses are simply reversed.
  1037.  
  1038. Gateway Type            8 for echo packet; 0 for echo reply.
  1039.  
  1040.  
  1041.  
  1042.  
  1043.  
  1044.  
  1045.  
  1046.  
  1047.  
  1048.  
  1049.  
  1050.  
  1051.  
  1052.  
  1053.  
  1054.  
  1055.  
  1056.  
  1057.  
  1058.  
  1059.  
  1060.  
  1061.  
  1062.  
  1063.  
  1064.  
  1065.  
  1066.  
  1067.  
  1068.  
  1069.  
  1070.  
  1071.  
  1072.  
  1073.  
  1074.  
  1075.  
  1076.                              - 17 -
  1077.  
  1078.  
  1079.  
  1080.  
  1081.  
  1082.  
  1083.                    Net Interface Status Packet
  1084.  
  1085.  0                   1                   2                   3
  1086.  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  1087. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1088. ! Gateway Type  !                  unused                       !
  1089. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  1090.  
  1091. Source Address
  1092. Destination Address     The address of the gateway's network
  1093.                         interface.  The gateway can send Net
  1094.                         Interface Status Packets to itself to
  1095.                         determine if it is able to send and
  1096.                         receive traffic on its network interface.
  1097.  
  1098.  
  1099. Gateway Type            9
  1100.  
  1101.  
  1102.  
  1103.  
  1104.  
  1105.  
  1106.  
  1107.  
  1108.  
  1109.  
  1110.  
  1111.  
  1112.  
  1113.  
  1114.  
  1115.  
  1116.  
  1117.  
  1118.  
  1119.  
  1120.  
  1121.  
  1122.  
  1123.  
  1124.  
  1125.  
  1126.  
  1127.  
  1128.  
  1129.  
  1130.  
  1131.  
  1132.  
  1133.  
  1134.  
  1135.                              - 18 -
  1136.  
  1137.  
  1138.  
  1139.  
  1140.  
  1141.  
  1142. 14.  Examples
  1143.  
  1144. The following examples illustrate the sequence number scheme
  1145. used for sending and receiving routing updates.
  1146.  
  1147. Example 1:
  1148.  
  1149. Gateway G has three neighbors:  A, B and C.
  1150. Gateway G's Send Sequence Number is 5.
  1151. Connectivity between gateway G and gateway A was broken and is
  1152. now restored; thus, A has not received the last update from G.
  1153. Gateway A's Receive Sequence Number for G is 3.
  1154. Gateway B's Receive Sequence Number for G is 4.
  1155. Gateway C's Receive Sequence Number for G is 4.
  1156.  
  1157. Initially, gateway G has the following values in its tables:
  1158.  
  1159. Send Sequence   Received Acknowledgement from Neighbors
  1160.                    A   B   C
  1161.      5             N   N   N  (N for no, Y for yes)
  1162.  
  1163.  
  1164. G (5) ---> A       G sends routing update 5 to its neighbors
  1165. G (5) ---> B
  1166. G (5) ---> C
  1167. A (ACK 5) ---> G   A computes (sequence number received in
  1168.                    packet - Receive Sequence Number) = (5-3); as
  1169.                    this is greater than or equal to zero, A
  1170.                    acknowledges routing update 5 and replaces
  1171.                    Receive Sequence Number for G with 5
  1172.  
  1173. B (ACK 5) ---> G   B computes (sequence number received in
  1174.                    packet - Receive Sequence Number) = (5-4); as
  1175.                    this is greater than or equal to zero, B
  1176.                    acknowledges routing update 5 and replaces
  1177.                    its Receive Sequence Number for G with 5
  1178.  
  1179. C (ACK 5) ---> G
  1180.  
  1181. On receipt of these acknowledgements, G computes (Send Sequence
  1182. Number - sequence number acknowledged) = (5-5).  As this value
  1183. is zero, G notes that each of its neighbors has acknowledged
  1184. its routing update.
  1185.  
  1186.  
  1187.  
  1188.  
  1189.  
  1190.  
  1191.  
  1192.  
  1193.  
  1194.                              - 19 -
  1195.  
  1196.  
  1197.  
  1198.  
  1199.  
  1200.  
  1201. Gateway G now has the following values in its tables:
  1202.  
  1203. Send Sequence   Received Acknowledgement from Neighbors
  1204.                    A   B   C
  1205.      5             Y   Y   Y
  1206.  
  1207. Gateway A's Receive Sequence Number for G is 5.
  1208. Gateway B's Receive Sequence Number for G is 5.
  1209. Gateway C's Receive Sequence Number for G is 5.
  1210.  
  1211.  
  1212.  
  1213.  
  1214.  
  1215.  
  1216.  
  1217.  
  1218.  
  1219.  
  1220.  
  1221.  
  1222.  
  1223.  
  1224.  
  1225.  
  1226.  
  1227.  
  1228.  
  1229.  
  1230.  
  1231.  
  1232.  
  1233.  
  1234.  
  1235.  
  1236.  
  1237.  
  1238.  
  1239.  
  1240.  
  1241.  
  1242.  
  1243.  
  1244.  
  1245.  
  1246.  
  1247.  
  1248.  
  1249.  
  1250.  
  1251.  
  1252.  
  1253.                              - 20 -
  1254.  
  1255.  
  1256.  
  1257.  
  1258.  
  1259.  
  1260. Example 2:
  1261.  
  1262. Gateway G has three neighbors:  A, B, and C.
  1263. Gateway G's Send Sequence Number is 24.
  1264. Gateway A has been disconnected from gateway G for some long time,
  1265. thus, it has missed many updates from G and G's Send Sequence Number
  1266. has now wrapped around.
  1267. Gateway A's Receive Sequence Number for G is 500.
  1268. Gateway B's Receive Sequence Number for G is 23.
  1269. Gateway C's Receive Sequence Number for G is 23.
  1270.  
  1271. Initially, gateway G has the following values in its tables:
  1272.  
  1273. Send Sequence   Received Acknowledgement from Neighbors
  1274.                    A   B   C
  1275.      24            N   N   N  (N for no, Y for yes)
  1276.  
  1277. G (24) ---> A       G sends routing update 24 to all its neighbors
  1278. G (24) ---> B
  1279. G (24) ---> C
  1280. A (NAK 500) ---> G  A computes (sequence number received in
  1281.                     packet - Receive Sequence Number) = (24-500);
  1282.                     as this is less than zero, A sends a negative
  1283.                     acknowledgement with sequence number 500
  1284.  
  1285. On receipt of the negative acknowledgement, gateway G computes
  1286. (Send Sequence Number - sequence number negatively acknowledged)
  1287. = (24-500).  As this value is less than zero, G replaces its Send
  1288. Sequence Number with 501 and retransmits the routing update with
  1289. this sequence number.
  1290.  
  1291. G (501) ---> A
  1292. G (501) ---> B
  1293. G (501) ---> C
  1294. A (ACK 501) ---> G  A computes (sequence number received in
  1295.                     packet - Receive Sequence Number) = (501-500);
  1296.                     as this is greater than or equal to zero,
  1297.                     A acknowledges sequence number 501 and
  1298.                     replaces its Receive Sequence Number for G
  1299.                     with 501
  1300.  
  1301. B (ACK 24) ---> G   B receives the update from G with sequence
  1302.                     number 24; B computes (sequence number received
  1303.                     in packet - Receive Sequence Number) = (24-23);
  1304.                     as this is greater than or equal to zero,
  1305.                     B acknowledges sequence number 24 and replaces
  1306.                     its Receive Sequence Number for G with 24
  1307.  
  1308. C (ACK 24) ---> G
  1309.  
  1310.  
  1311.  
  1312.                              - 21 -
  1313.  
  1314.  
  1315.  
  1316.  
  1317.  
  1318.  
  1319. On receipt of these acknowledgements, G computes (Send Sequence
  1320. Number - sequence number acknowledged) = (501-24).  As this value
  1321. is non-zero, G retransmits the routing update to these neighbors.
  1322.  
  1323. G (501) ---> B
  1324. G (501) ---> C
  1325. B (ACK 501) ---> G  B computes (sequence number received in
  1326.                     packet - Receive Sequence Number) = (501-24);
  1327.                     as this is greater than or equal to zero,
  1328.                     B acknowledges sequence number 501 and
  1329.                     replaces its Receive Sequence Number for G
  1330.                     with 501
  1331.  
  1332.  
  1333. C (ACK 501) ---> G
  1334.  
  1335. On receipt of these acknowledgements, G computes (Send Sequence
  1336. Number - sequence number acknowledged) = (501-501).  As this value
  1337. is zero, G notes that each of its neighbors has acknowledged
  1338. its routing update.
  1339.  
  1340. Gateway G now has the following values in its tables:
  1341.  
  1342. Send Sequence   Received Acknowledgement from Neighbors
  1343.                    A   B   C
  1344.      501           Y   Y   Y
  1345.  
  1346. Gateway A's Receive Sequence Number for G is 501.
  1347. Gateway B's Receive Sequence Number for G is 501.
  1348. Gateway C's Receive Sequence Number for G is 501.
  1349.  
  1350.  
  1351.  
  1352.  
  1353.  
  1354.  
  1355.  
  1356.  
  1357.  
  1358.  
  1359.  
  1360.  
  1361.  
  1362.  
  1363.  
  1364.  
  1365.  
  1366.  
  1367.  
  1368.  
  1369.  
  1370.  
  1371.                              - 22 -
  1372.  
  1373.  
  1374.  
  1375.  
  1376.  
  1377.  
  1378. 15.  Tables and Variables
  1379.  
  1380. The following is a list of variables  and  tables  in  a  typical
  1381. gateway implementation.
  1382.  
  1383. 1.  Number of Networks
  1384.  
  1385. 2.  Number of Neighbors
  1386.  
  1387. 3.  Gateway Addresses
  1388.  
  1389. The addresses of the gateway's network interfaces.
  1390.  
  1391. 4.  Neighbor Gateway Addresses
  1392.  
  1393. The address of each gateway network interface that is on the same
  1394. network as this gateway.
  1395.  
  1396. 5.  Neighbor Connectivity Vector
  1397.  
  1398. A vector of the connectivity between this gateway and each of its
  1399. neighbors.   It  contains  K  entries  where  K  is the Number of
  1400. Neighbors.  Values in this vector are computed  as  explained  in
  1401. "Determining Connectivity to Neighbors".
  1402.  
  1403. 6.  Distance Matrix
  1404.  
  1405. A  matrix  of  the  routing  updates  received  from the neighbor
  1406. gateways.
  1407.  
  1408. 7.  Minimum Distance Vector
  1409.  
  1410. A vector containing the minimum distance to each network.  It  is
  1411. computed as described in "Computing Routes".
  1412.  
  1413. 8.  Routing Updates
  1414.  
  1415. A  set  of  vectors giving the distance from this gateway to each
  1416. network.  There is a separate vector to be sent to each neighbor.
  1417. These are computed as described in "Computing Routes".
  1418.  
  1419. 9.  Routing Updates from Non-Routing Gateways
  1420.  
  1421. The routing updates that  would  have  been  received  from  each
  1422. neighbor  gateway  that  does  not  participate  in  this routing
  1423. strategy.   These  are  computed  as  described  in  "Non-Routing
  1424. Gateways".
  1425.  
  1426.  
  1427.  
  1428.  
  1429.  
  1430.                              - 23 -
  1431.  
  1432.  
  1433.  
  1434.  
  1435.  
  1436.  
  1437. 10.  Routing Table
  1438.  
  1439. A  table  containing,  for  each  network, a list of the neighbor
  1440. gateways on a minimum distance route to  the  network.   This  is
  1441. computed as described in "Computing Routes".
  1442.  
  1443. 11.  Send Sequence Number
  1444.  
  1445. The  sequence  number  that will be used to send the next routing
  1446. update.
  1447.  
  1448. 12.  Receive Sequence Numbers
  1449.  
  1450. The sequence numbers  that  the  gateway  received  in  the  last
  1451. routing update from each of its neighbors.
  1452.  
  1453. 13.  Received Acknowledgement Vector
  1454.  
  1455. A vector indicating whether or not each neighbor has acknowledged
  1456. the sequence number in the most recent routing update sent.
  1457.  
  1458.  
  1459.  
  1460.  
  1461.  
  1462.  
  1463.  
  1464.  
  1465.  
  1466.  
  1467.  
  1468.  
  1469.  
  1470.  
  1471.  
  1472.  
  1473.  
  1474.  
  1475.  
  1476.  
  1477.  
  1478.  
  1479.  
  1480.  
  1481.  
  1482.  
  1483.  
  1484.  
  1485.  
  1486.  
  1487.  
  1488.  
  1489.                              - 24 -
  1490.  
  1491.  
  1492.  
  1493.  
  1494.  
  1495.  
  1496. 16.  Events and Responses
  1497.  
  1498. The following is a list of the events that occur at a gateway and
  1499. the  gateway's  responses.   The variables and tables referred to
  1500. are listed above.  This is a general guide for an implementation;
  1501. see  the  sections  above  for  the  details   of   the   various
  1502. computations.
  1503.  
  1504. 1.   Connectivity  to  a network to which the gateway is attached
  1505. changes.
  1506.  
  1507.         1.  Update the Minimum Distance Vector.
  1508.  
  1509.         2.  Recompute the Routing Updates.
  1510.  
  1511.         3.  Recompute the Routing Table.
  1512.  
  1513.         4.  If any routing  update  has  changed,  send  the  new
  1514.         routing updates to the neighbors.
  1515.  
  1516. 2.  Connectivity to a neighbor gateway changes.
  1517.  
  1518.         1.  Update the Neighbor Connectivity Vector.
  1519.  
  1520.         2.  Recompute the Minimum Distance Vector.
  1521.  
  1522.         3.  Recompute the Routing Updates.
  1523.  
  1524.         4.  Recompute the Routing Table.
  1525.  
  1526.         5.   If  any  routing  update  has  changed, send the new
  1527.         routing updates to the neighbors.
  1528.  
  1529.  
  1530. 3.  A Routing Update Packet is received.
  1531.  
  1532.         1.  Compare the internet source address  of  the  Routing
  1533.         Update  Packet to the Neighbor Addresses.  If the address
  1534.         is not on the list,  add  it  to  the  list  of  Neighbor
  1535.         Addresses, increment the Number of Neighbors, and set the
  1536.         Receive Sequence Number for this neighbor to the sequence
  1537.         number in the Routing Update Packet.
  1538.  
  1539.         2.  Compare the Receive Sequence Number for this neighbor
  1540.         to  the  sequence  number in the Routing Update Packet to
  1541.         determine whether or not to accept this packet.   If  the
  1542.         packet  is  rejected,  send  a  Negative  Acknowledgement
  1543.         Packet.    If   the   packet   is   accepted,   send   an
  1544.         Acknowledgement  Packet  and  proceed  with the following
  1545.         steps.
  1546.  
  1547.  
  1548.                              - 25 -
  1549.  
  1550.  
  1551.  
  1552.  
  1553.  
  1554.  
  1555.         3.  Compare the number of networks  reported  on  in  the
  1556.         Routing  Update Packet to the Number of Networks.  If the
  1557.         number of networks in the  packet  is  greater  than  the
  1558.         Number  of Networks, then replace Number of Networks with
  1559.         the  number  of  networks  in  the  packet.   Expand  the
  1560.         Distance Matrix to account for the new networks.
  1561.  
  1562.         4.  Copy the routing update received into the appropriate
  1563.         row of the Distance Matrix.
  1564.  
  1565.         5.  Recompute the Minimum Distance Vector.
  1566.  
  1567.         6.  Recompute the Routing Updates.
  1568.  
  1569.         7.  Recompute the Routing Table.
  1570.  
  1571.         8.   If  any  routing  update  has  changed, send the new
  1572.         routing updates to the neighbors.
  1573.  
  1574. 4.  An Acknowledgement  or  Negative  Acknowledgement  Packet  is
  1575. received.
  1576.  
  1577.         1.  Compare the sequence number in the packet to the Send
  1578.         Sequence Number.  If necessary, replace the Send Sequence
  1579.         Number,  and retransmit the routing updates.  If the Send
  1580.         Sequence Number is acknowledged, update the entry in  the
  1581.         Received Acknowledgment Vector for the neighbor that sent
  1582.         the acknowledgement.
  1583.  
  1584. 5.  A data packet is received.
  1585.  
  1586.         1.   Forward the data packet using the information in the
  1587.         Routing Table entry for the packet's destination network.
  1588.  
  1589.         2.  If the destination is unreachable, send a Destination
  1590.         Unreachable Packet to the internet  source  of  the  data
  1591.         packet.
  1592.  
  1593.         3.   If the data packet is discarded because there are no
  1594.         buffers available in the  gateway,  then  send  a  Source
  1595.         Quench  Packet to the internet source of the data packet.
  1596.  
  1597.         4.  If the gateway to which  the  data  packet  is  being
  1598.         forwarded  and  the  data packet's internet source are on
  1599.         the same network, send a Redirect Packet to the  internet
  1600.         source of the data packet.
  1601.  
  1602.  
  1603.  
  1604.  
  1605.  
  1606.  
  1607.                              - 26 -
  1608.  
  1609.